我们前面提到权转移法的本质是搜索某个图族的不可回避集的方法. 如果换一个角度,我们会发现, 权转移法的另一个本质是: \textbf{一种计数方法}. 为了展现这一点,我们给出例\ref{emp:ch-in-2}的另一个证明.
\vskip 10pt
\begin{proof}
设$G$是一个最小度为$5$的平面三角剖分图.
假设$G$不包含$(6^-,5,6^-)$-路.
给$G$的顶点和面设置初始电荷量$ch_0(\cdot)$如下:
[
ch_0(x)=\left{
\begin{aligned}
& 0, & x\in V(G)
& 1, & x\in F(G)
\end{aligned}
\right.
]
那么$G$的总电荷量就是$f(G)$.下面给出放电规则.
\begin{discharge}
\textbf{规则1.} 面$f$向它所关联的每个$6$-顶点转移$1/3$个电荷.
\textbf{规则2.} 如果面$f$只关联一个$5$-顶点$v$,不关联$6$-顶点,
那么,$f$向$v$转移$1$个电荷.
\textbf{规则3.} 如果面$f$恰好关联一个$5$-顶点$v$,一个$6$-顶点,
那么,$f$向$v$转移$2/3$个电荷.
\textbf{规则4.} 如果面$f$恰好关联两个$5$-顶点$u,v$,不关联$6$-顶点,
那么,$f$分别向$u$和$v$转移$1/2$个电荷.
\end{discharge}
设放电之后的电荷量为$ch_1(\cdot)$.设$v\in V(G)$.
如果$\deg(v)\ge7$,那么$ch_1(v)=0$.
如果$\deg(v)=6$,那么$ch_1(v)=2$.
如果$\deg(v)=5$,因为我们假设$G$没有$(6^-,5,6^-)$-路,
所以$v$的$6^-$-邻点至多一个,
那么$ch_1(v)\ge4$.
设$f\in F(G)$,
因为条件给定$G$是三角剖分图,所以$\deg(f)=3$.
如果$f$只关联$6^+$-顶点,那么$ch_1(f)\ge0$.
如果$f$关联了$5$-顶点$v$,
因为我们假设$G$不含$(6^-,5,6^-)$-路,
所以$f$所关联的另外两个顶点,至多一个是$6^-$-顶点.
如果除了$5$-顶点$v$之外,$f$还关联一个$5$-顶点,
那么$ch_1(f)=1-1/2-1/2=0$.
如果除了$5$-顶点$v$之外,$f$还关联了一个$6$-顶点,
那么$ch_1(f)=1-2/3-1/3=0$.
总之,如果我们记$d$-顶点的个数为$n_d$,
那么在放电之后,总的电荷量至少为$4n_5+2n_6$.
所以\[f(G)\ge 4n_5+2n_6.\]
但是另一方面,由欧拉公式可得
\[2=v(G)-e(G)+f(G)=\sum_{d\ge 5}(n_d-\frac{1}{2}dn_d+\frac{1}{3}dn_d)
=\frac{1}{6}\sum_{d\ge 5}(6-d)n_d.\]
所以,
\[12+v(G)=\sum_{d\ge5}(7-d)n_d=2n_5+n_6+\sum_{d\ge8}(7-d)n_d
\le2n_5+n_6\le \frac{1}{2}f(G),\]
所以,$f(G)\ge 2v(G)+24$,
这与$f(G)\le 2v(G)-4$矛盾. \end{proof}
其实,这个证明与上一节的证明有某种本质上的相通性(但我没想明白). 这个结论其实是Franklin在研究了Wernicke的结论(即例\ref{emp:ch-in-1})后所做的改进. 本节给出的证明是Franklin的原始证明,上一节是我们用现代更常见的形式写出的证明. 然而,Wernicke和Franklin的目的都不仅仅是证明这样两个结构上的结论, 他们研究这两个问题的着眼点都是为了证明四色定理. 这正是权转移法的最著名的应用, 事实上,权转移法的发明最初也就是为了研究四色问题. 那么,染色这种问题是如何用上权转移法的呢?我们需要第三个例子.